import java.util.ArrayList;

public class RegularExpressionMatching {
	public void tester()
	{
		System.out.println(isMatch("aa",".*"));
	}
	
    public boolean isMatch(String s, String p) {
        
        int i = 0, j = 0;
        
        while(i < s.length() || j<p.length())
        {
            if(j+1<p.length() && p.charAt(j+1) == '*')
            {
                if(i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'))
                {
                    enqueue(i, j+2);
                    i++;
                }
                else
                {
                    j = j+2;
                }
            }
            else if(j < p.length() && i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.')) // normal case
            {
                i++;
                j++;
            }
            else
            {
                if(notEmpty())
                {
                    i = geti();
                    j = getj();
                }
                else
                {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    ArrayList <Integer> q_i = new ArrayList <Integer> ();
    ArrayList <Integer> q_j = new ArrayList <Integer> ();
    public void enqueue(int i, int j)
    {
        q_i.add(i);
        q_j.add(j);
    }
    
    public boolean notEmpty()
    {
        if(q_i.size() > 0) return true;
        else return false;
    }
    
    public int geti()
    {
        int x = q_i.get(q_i.size()-1);
        q_i.remove(q_i.size()-1);
        return x;
    }
    
    public int getj()
    {
        int x = q_j.get(q_j.size()-1);
        q_j.remove(q_j.size()-1);
        return x;
    }
}
